package bubble

import (
	"fmt"
	"t_sort/data"
)

func Sort[T data.SortType](arr []T) {
	for i := 0; i < len(arr)-1; i++ {
		for j := len(arr) - 1; j > i; j-- {
			if arr[j] < arr[j-1] {
				arr[j], arr[j-1] = arr[j-1], arr[j]
			}
		}
		fmt.Println(arr)
	}
}

var count = 0 //

// Sort1 第一版 todo 1.下标越界（控制内层循环的进入条件）
func 暴力冒泡(数组 []int) {
	for i := 0; i < len(数组); i++ {
		for j := 0; j < len(数组)-1; j++ {
			count++
			if 数组[j] > 数组[j+1] {
				数组[j], 数组[j+1] = 数组[j+1], 数组[j]
			}
			fmt.Printf("轮数:%d 第%d次：%v \n", i+1, count, 数组)
		}
	}
}

// Sort2 第二版 todo 比较次数优化 区分有序数组
func 无序数组冒泡(数组 []int) {
	for i := 0; i < len(数组)-1; i++ {
		for j := 0; j < len(数组)-1-i; j++ {
			count++
			if 数组[j] > 数组[j+1] {
				数组[j], 数组[j+1] = 数组[j+1], 数组[j]
			}
			fmt.Printf("轮数:%d 第%d次：%v \n", i+1, count, 数组)
		}
	}
}

// Sort3 第三版 todo 终止无效比较
func Sort3(数组 []int) {
	var sorted bool
	for i := 0; i < len(数组)-1; i++ {
		sorted = true
		for j := 0; j < len(数组)-1-i; j++ {
			count++
			if 数组[j] > 数组[j+1] {
				数组[j], 数组[j+1] = 数组[j+1], 数组[j]
				sorted = false
			}
			fmt.Printf("轮数:%d 第%d次：%v \n", i+1, count, 数组)
		}
		if sorted {
			break
		}
	}
}

// Sort4 第三版 todo 动态判断有序数组长度
func Sort4(arr []int) {
	var sorted bool
	lastExIndex, sortBorder := 0, len(arr)-1
	for i := 0; i < len(arr)-1; i++ {
		sorted = true
		for j := 0; j < sortBorder; j++ {
			count++
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
				sorted = false
				lastExIndex = j
			}
			fmt.Printf("轮数:%d 第%d次：%v \n", i+1, count, arr)
		}
		sortBorder = lastExIndex
		if sorted {
			break
		}
	}
}
